package alg;

/**
 * 斐波那契
 * @author xiaoyunnshi
 * @date 2021/8/24 下午4:39
 */
public class Fib {
    public static void main(String[] args) {
        // 6765
        int x=50;
        long s=System.currentTimeMillis();
        System.out.println(fib(x));
        long s2=System.currentTimeMillis();
        System.out.println(s2-s);
        System.out.println("-------");

        System.out.println(fib_dp(x));
        long s3=System.currentTimeMillis();
        System.out.println(s3-s2);
        System.out.println("-------");

        System.out.println(fib_dp0(x));
        System.out.println(System.currentTimeMillis()-s3);


    }

    static long fib(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        return fib(n - 1) + fib(n - 2);
    }

    static long fib_dp0(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        long[] dp = new long[n + 2];
        dp[1] = dp[2] = 1;
        for (int i = 3; i <=n; i++) {
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }

    static long fib_dp(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        long pre = 1, prePre = 1;
        long cur = 0;
        for (long i = 3; i <= n; i++) {
            cur = pre + prePre;
            pre = prePre;
            prePre = cur;
        }
        return cur;
    }
}
